package medium

import (
	. "GoLeetcode/common"
	"sort"
)

/*
时间复杂度:O(n^2)
空间复杂度:O(1)

方法一:排序+双指针
*/
func triangleNumber(nums []int) int {
	sort.Ints(nums)
	ans := 0
	for i, v := range nums {
		// 这里k与j是同一层循环, k的值随着j的左移而左移
		k := i + 2
		for j := i + 1; j < len(nums); j++ {
			for k < len(nums) && v+nums[j] > nums[k] {
				k++
			}
			// 有可能k-j-1为负数
			ans += Max(k-j-1, 0)
		}
	}
	return ans
}

/*
时间复杂度:O(n^2logn) i j双层循环n^2, 每次循环对nums进行二分查找O(logn), 最后n^2logn
空间复杂度:O(logn) 排序所需要的空间

方法二:排序+二分查找
*/
func triangleNumber1(nums []int) int {
	sort.Ints(nums)
	ans := 0
	for i, v := range nums {
		for j := i + 1; j < len(nums); j++ {
			// 对nums[j+1:]进行二分查找,找到第一个大于等于v+nums[j]的值对应的索引
			ans += sort.SearchInts(nums[j+1:], v+nums[j])
		}
	}
	return ans
}
